package kbl.language;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

public class NFA implements StrategyRE2NFA {
	// nondeterministic finite automaton
	/**
	 * SingletonHolder is loaded on the first execution of
	 * Singleton.getInstance() or the first access to SingletonHolder.INSTANCE,
	 * not before.
	 */
	private NFA() {
	}

	private static class SingletonHolder {
		public static final NFA INSTANCE = new NFA();
	}

	public static NFA getInstance() {
		return SingletonHolder.INSTANCE;
	}

	class NFAFrame {
		private NFAState start;
		private ArrayList<NFAState> end;

		NFAFrame(NFAState start, ArrayList<NFAState> end) {
			this.start = start;
			this.end = end;
		}

		public NFAState getStart() {
			return this.start;
		}

		public void setStart(NFAState s) {
			this.start = s;

		}

		public ArrayList<NFAState> getEnd() {
			return this.end;
		}

		public void patch(NFAState s) {
			for (NFAState e : end) {
				e.setOut(s);
			}
			end.clear();
		}

		public void append(ArrayList<NFAState> c) {
			this.end.addAll(c);
		}

		public void append(NFAState c) {
			this.end.add(c);
		}

	}

	private Set<NFAState> CurrentStateSet = new HashSet<NFAState>();
	private Set<NFAState> NextStateSet = new HashSet<NFAState>();
	private int stateCount = 0;
	private int matchCount = Integer.MIN_VALUE;
	private NFAState root;
	private NFAState current;
	Stack<NFAFrame> NFAStack = new Stack<NFAFrame>();

	@Override
	public NFAState getRootNFA() {
		return root;
	}

	@Override
	public NFAState getCurrentNFA() {
		return current;
	}

	@Override
	public void clearRootNFA() {
		root = null;
	}

	@Override
	public NFAState addNFA(RegularExpression postfixRE) {
		RE2NFA(postfixRE);
		if (root == null) {
			root = current;
		} else {
			NFAState s = new NFAState(this);
			s.setOut(root);
			s.setAltout(current);
			root = s;
		}
		return root;
	}

	@Override
	public NFAState RE2NFA(RegularExpression postfixRE) {
		for (RElement e : postfixRE.getListRe()) {
			processRE(e);
		}
		NFAStack.peek().patch(new Match(this, postfixRE.getName()));
		current = NFAStack.pop().getStart();
		return current;
	}

	private void processRE(RElement re) {
		NFAFrame e2;
		NFAFrame e1;
		NFAState s;
		ArrayList<NFAState> c;
		switch (re.getOperator()) {
		case Alternate: /* alternate */
			e2 = NFAStack.pop();
			e1 = NFAStack.pop();
			s = new NFAState(this);
			s.setOut(e1.getStart());
			s.setAltout(e2.getStart());
			e1.setStart(s);
			e1.append(e2.getEnd());
			NFAStack.push(e1);
			break;
		case QuestionMark: /* zero or one */
			e1 = NFAStack.pop();
			s = new NFAState(this);
			s.setAltout(e1.getStart());
			e1.setStart(s);
			e1.append(s);
			NFAStack.push(e1);
			break;
		case Asterisk: /* zero or more */
			e1 = NFAStack.pop();
			s = new NFAState(this);
			s.setAltout(e1.getStart());
			e1.patch(s);
			e1.setStart(s);
			e1.append(s);
			NFAStack.push(e1);
			break;
		case Plus: /* one or more */
			e1 = NFAStack.pop();
			s = new NFAState(this);
			s.setAltout(e1.getStart());
			e1.patch(s);
			e1.append(s);
			NFAStack.push(e1);
			break;
		case Concatenate: /* concatenate */
			e2 = NFAStack.pop();
			e1 = NFAStack.pop();
			e1.patch(e2.getStart());
			e1.append(e2.getEnd());
			NFAStack.push(e1);
			break;
		case Literal:
			s = new NFAState(this, re.getLiteral());
			c = new ArrayList<NFAState>();
			c.add(s);
			NFAStack.push(new NFAFrame(s, c));
			break;
		case CharacterClass:
			s = new NFAState(this, re.getCC());
			c = new ArrayList<NFAState>();
			c.add(s);
			NFAStack.push(new NFAFrame(s, c));
			break;
		default:
			System.err.println("Error: unhandle REType.");
			System.exit(1);
		}
	}

	@Override
	public void incStatecount() {
		this.stateCount++;
	}

	@Override
	public int getStatecount() {
		return stateCount;
	}

	@Override
	public void incMatchcount() {
		this.matchCount++;
	}

	@Override
	public int getMatchcount() {
		return matchCount;
	}

	public boolean match(RegularExpression postfixRE, String input) {
		NFAState s = RE2NFA(postfixRE);
		return match(s, input);
	}

	public boolean match(String input) {
		return match(root, input);
	}

	private boolean match(NFAState s, String input) {
		CurrentStateSet.clear();
		NextStateSet.clear();
		Set<NFAState> t;
		addState(CurrentStateSet, s);
		for (char i : input.toCharArray()) {
			step(i);
			t = CurrentStateSet;
			CurrentStateSet = NextStateSet;
			NextStateSet = t;
		}

		for (NFAState s1 : CurrentStateSet) {
			if (s1.isMatch()) {
				return true;
			}
		}
		return false;
	}

	private void step(char c) {
		NextStateSet.clear();
		for (NFAState s : CurrentStateSet) {
			if (s.match(c)) {
				addState(NextStateSet, s.getOut());
			}

		}
	}

	private void addState(Set<NFAState> currentStateSet2, NFAState s) {
		if (s.isEpsilon()) {
			addState(currentStateSet2, s.getOut());
			addState(currentStateSet2, s.getAltout());
		} else {
			currentStateSet2.add(s);
		}
	}

}
